package com.tgy.leetcode;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @Author: tgy
 * @Date: 2/3/21 9:26 AM
 *
 *  https://leetcode-cn.com/problems/sliding-window-median/
 */
public class _480_滑动窗口中位数_01 {

    public static double[] medianSlidingWindow(int[] nums, int k) {

        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> {
            return Integer.compare(o2, o1);
        });

        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        double[] res = new double[nums.length - k + 1];

        for (int i = 0; i < k; ++i) {

            maxHeap.offer(nums[i]);
        }

        // 3
        int count = k >> 1;

        for (int i = 0; i < count; i++) {

            minHeap.offer(maxHeap.poll());
        }

        boolean isOdd = (k & 1) == 1;

        for (int i = k; i <= nums.length; i++) {

            int preIndex = i - k;
            if (isOdd) {

                res[preIndex] = maxHeap.peek();
            }else {

                res[preIndex] = (minHeap.peek() - maxHeap.peek()) / 2.0 + maxHeap.peek();
            }

            if (i == nums.length) {
                break;
            }

//            nums[i - k]
            if (nums[preIndex] <= maxHeap.peek()) {
                //1
                maxHeap.remove(nums[preIndex]);

                if (!minHeap.isEmpty() && nums[i] <= maxHeap.peek()) {

                    maxHeap.offer(nums[i]);
                }else {

                    //1+2
                    minHeap.offer(nums[i]);
                    maxHeap.offer(minHeap.poll());
                }
            }else {

                minHeap.remove(nums[preIndex]);

                if (!minHeap.isEmpty() && nums[i] >= minHeap.peek()) {

                    minHeap.offer(nums[i]);
                }else {

                    maxHeap.offer(nums[i]);
                    minHeap.offer(maxHeap.poll());
                }
            }

        }

        return res;
    }



    public static void main(String[] args) {


//        PriorityQueue<Integer> queue = new PriorityQueue<>();
//
//        queue.offer(1);
//        queue.offer(3);
//        queue.offer(-1);
//
//        System.out.println(queue.peek());
//
//        queue.remove(1);
//        queue.offer(-3);
//
//        System.out.println(queue.peek());

        int[] nums = {-2147483648,-2147483648,2147483647,-2147483648,-2147483648,-2147483648,2147483647,2147483647,2147483647,2147483647,-2147483648,2147483647,-2147483648};

//        int[] nums = {1,3,-1,-3,5,3,6,7};

        double[] res = medianSlidingWindow(nums, 3);

        System.out.println(Arrays.toString(res));
    }
}
